﻿// 0801train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <limits.h>

using namespace std;


/*
 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列 。
 第一个差（如果存在的话）可能是正数或负数。
 仅有一个元素或者含两个不等元素的序列也视作摆动序列。
- 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
- 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，
第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例1
输入：nums = [1,7,4,9,2,5]
输出：6

示例2
输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
 */

void solve01(vector<int>& nums)
{
	vector<int>oh_vec = nums;
	int vec_size = oh_vec.size();
	int init_state = 0;
	int up_state = 1;
	int down_state = 2;

	int state = 0;
	vector<int>result_vec = {oh_vec[0]};
	for (int i=1; i<vec_size; i++)
	{
		if (state==init_state)
		{
			if (oh_vec[i]<oh_vec[i-1])
			{
				state = down_state;
				result_vec.push_back(oh_vec[i]);
			}
			else if (oh_vec[i]>oh_vec[i-1])
			{
				state = up_state;
				result_vec.push_back(oh_vec[i]);
			}
		}
		else if (state==up_state)
		{
			if (oh_vec[i]<oh_vec[i-1])
			{
				state = down_state;
				result_vec.push_back(oh_vec[i]);
			}
			else
			{
				int result_size = result_vec.size();
				result_vec[result_size - 1] = oh_vec[i];
			}
		}
		else if (state==down_state)
		{
			if (oh_vec[i]>oh_vec[i-1])
			{
				state = up_state;
				result_vec.push_back(oh_vec[i]);
			}
			else
			{
				int result_size = result_vec.size();
				result_vec[result_size - 1] = oh_vec[i];
			}
		}
		//for------
	}

	//for (auto&num:result_vec)
	//{
	//	cout << num << ' ';
	//}

	//cout << '\n';
	//cout << result_vec.size();
	//solve01
}


/*
试计算出该货车最多能运载的快递数目。快递数量最多为1000个，货车的最大载重最为50000。
注：不考虑快递的体积。
输入
第一行输入每个快递的重量，用英文逗号隔开，如 5,10,2,11
第二行输入货车的最大载重量，如 20
输出
输出最多能装多少个快递，如 3

输入
5,10,2,11
20

输出
3
 */
void solve02(vector<int>&oh_vec, int target)
{
	sort(oh_vec.begin(), oh_vec.end());

	int curr_sum = 0;
	int count = 0;
	for (auto&num:oh_vec)
	{
		curr_sum += num;
		if (curr_sum > target) break;
		count += 1;
	}
	cout << count;
	//solve02------
}


/*
停车场有一横排车位，0 代表没有停车，1 代表有车。至少停了一辆车在车位上，也至少有一个空位没有停车。
为了防剐蹭，需为停车人找到一个车位，使得距停车人的车最近的车辆的距离是最大的，返回此时的最大距离。
输入描述
1、一个用半角逗号分割的停车标识字符串，停车标识为 0 或 1，0 为空位，1 为已停车。
2、停车位最多 100 个。
输出描述
输出一个整数记录最大距离。

输入
1,0,0,0,0,1,0,0,1,0,1
输出
2
 */
int GetLeftDistance(vector<int>& oh_vec, int target)
{
	//0,i
	if (target == 0) return-1;
	int index_1 = -1;
	int curr_index = target-1;
	while (curr_index>=0)
	{
		if (oh_vec[curr_index]==1)
		{
			index_1 = curr_index;
			break;
		}
		curr_index--;
	}

	if (index_1!=-1)
	{
		return target-index_1;
	}

	return target+1;
}

int GetRightDistance(vector<int>& oh_vec, int target)
{
	//i
	if (target==9)
	{
		cout << "test";
	}
	int vec_size = oh_vec.size();
	if (target == vec_size-1) return-1;
	int index_1 = -1;
	int curr_index = target + 1;

	while (curr_index <=vec_size-1)
	{
		if (oh_vec[curr_index]==1)
		{
			index_1 = curr_index;
			break;
		}
		curr_index++;
	}
	if (index_1!=-1)
	{
		return index_1-target;
	}
	return target + 1;
}

void solve03(vector<int>&oh_vec)
{
	int vec_size = oh_vec.size();
	int result = 0;

	for (int i=0; i<vec_size; i++)
	{
		int curr_num = oh_vec[i];
		if (curr_num != 0)continue;

		int left_count = GetLeftDistance(oh_vec, i);
		int right_count = GetRightDistance(oh_vec, i);
		
		int count = min(left_count, right_count);
		if (i==0)
		{
			count = right_count;
		}
		if (i==vec_size-1)
		{
			count = left_count;
		}
		if (count>result)
		{
			cout <<"max: "<< i << endl;
			cout << "result: " << result << " count: " << count << endl;
		}
		result = max(count, result);
		//for-----
	}
	cout << result;
	//solve03
}

int main()
{
	{
		//1,0,0,0,0,1,0,0,1,0,1
		//1,1,0,0,1,0,0,0,0,0,1
		vector<int>oh_vec = { 1,1,0,0,1,0,0,0,0,0,1 };

		//cout << GetRightDistance(oh_vec, 2);
		//string input;
		//getline(cin, input);
		//stringstream oh_sstream(input);
		//string token;
		//vector<int>oh_vec;

		//while (getline(oh_sstream, token, ','))
		//{
		//	oh_vec.push_back(stoi(token));
		//}

		//for (auto&item:oh_vec)
		//{
		//	cout << item << ' ';
		//}

		solve03(oh_vec);

		return 0;
	}

	{
		//5,10,2,11 20
		//vector<int>oh_vec = { 5,10,2,11 };
		//int target = 20;

		string input;
		getline(cin, input);
		stringstream oh_sstream(input);
		vector<int>oh_vec;
		string token;
		while (getline(oh_sstream, token, ','))
		{
			oh_vec.push_back(stoi(token));
		}
		int target;
		cin >> target;

		//for (auto&item:oh_vec)
		//{
		//	cout << item << ' ';
		//}
		//cout << '\n';
		//cout << target;

		solve02(oh_vec, target);

		return 0;
	}

	//nums = [1,17,5,10,13,15,10,5,16,8] 7
	//nums = [1,7,4,9,2,5] 6
	vector<int>nums = { 1,7,4,9,2,5 };
	solve01(nums);

	//main------
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
